package com.example.javabasic.suanfa.剑指offer.串联所有单词子串;

import java.util.*;

/**
 * @description
 * @Author Lin FuYuan
 * @date 2021/7/7
 * <p>
 * 给定一个字符串 s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
 * <p>
 * 注意子串要与 words 中的单词完全匹配，中间不能有其他字符 ，但不需要考虑 words 中单词串联的顺序。
 * <p>
 * 来源：力扣（LeetCode） 30
 * 链接：https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {


    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("foo");
        list.add("bar");
        String s  ="foobarfoobar";
        Solution solution = new Solution();
        List<Integer> substring = solution.findSubstring(s, list.toArray(new String[list.size()]));
        System.out.println(substring);
    }

    public List<Integer> findSubstring(String s, String[] words) {
        //求出组合set 集合
        Set<String> strings = zuheString(Arrays.asList(words));
        int wordLength = 0;
        for (String word : words) {
            wordLength += word.length();
        }
        char[] chars = s.toCharArray();
        List<Integer> list = new ArrayList<>();
        for (int i = chars.length - wordLength ; i >= 0; i--) {
            char[] c = Arrays.copyOfRange(chars, i, i + wordLength);
            String s1 = new String(c);
            System.out.println(s1);
            if(strings.contains(s1)){
                list.add(i);
            }
        }
        return list;
    }


    /**
     * 字符串拼接方式
     *
     * @return
     * @author Lin FuYuan
     * @date 2021/7/7
     */

    public  Set<String> zuheString(List<String> words) {
        Set<String> set = new HashSet<>();
        if(words == null){
            return set;
        }
        if(words.size() == 1){
            set.add(words.get(0));
            return set;
        }
        for (int i = 0; i < words.size(); i++) {
            List<String> newList = new ArrayList<>(words);
            newList.remove(i);
            Set<String> strings = zuheString(newList);
            for (String s : strings) {
                set.add(words.get(i) + s);
            }
        }
        return set;
    }


}
